A communication system is formed, at a minimum, by a transmitter and a receiver interconnected by a communication channel. The transmitter forms at least a portion of a sending station, and the receiver forms at least a portion of a receiving station. Information to be communicated by the transmitter to the receiver is modulated to form communication signals. The communication signals generated and transmitted by the sending station are transmitted upon the communication channel to be received by the receiving station. Information contained in the communication signals transmitted by the sending station is recovered once received at the receiving station. In a digital communication system, information to be communicated to the receiving station is digitized. The digitized information is then used to form the communication signal.
A radio communication system is a type of communication system in which the communication channel is formed of a radio channel defined upon a portion of the electromagnetic spectrum. Because a fixed connection is not required to form the communication channel between a sending and receiving station, communications are possible when a fixed connection between the sending an receiving station is impractical. However, radio channels are inherently public in nature. That is to say, a communication signal transmitted upon a radio communication channel can be detected by any receiving station tuned to the radio channel. An unauthorized party, for instance, is able to tune a radio receiver to the frequency of the radio channel upon which the communication signal is transmitted, thereby to receive the communication signal.
Privacy of communications effectuated in a radio communication system are difficult to assure due to the public nature of a radio communication channel. To increase the privacy of communications in such a communication system, cryptographic techniques are utilized to form encoded, or encrypted, signals. In other communication systems, such cryptographic techniques are also utilized to assure better the privacy of communications between a sending and receiving station.
A digital information signal is particularly amenable to be encoded or encrypted. A digital information signal is formed of sequences of bits which are modulated and transmitted during operation of a digital communication system. The bit-wise nature of a digital information signal is particularly amenable to be encoded or encrypted. Each bit, if desired, of which a digital information signal is formed, can be encoded at the sending station. An encoded communication signal is thereby formed which can be transmitted upon the radio communication channel to a receiving station. An unauthorized party having a radio receiver tuned to the radio channel upon which the encoded communication signal is transmitted is unable to decode the signal received thereat without knowledge of the encoding technique by which the encoded signal is formed. Only a receiving station capable of decoding the encoded signal is able to recover the informational content of the encoded signal transmitted upon the communication channel.
Various manners are used by which to encode or otherwise encrypt a digital information signal. A typical encoding scheme, such as that used in cellular communications, utilizes an encryption process by which the bits of an information signal are encoded by combining the bits with pseudo-random sequence generated by a pseudo-random sequence generator. The pseudo-random signal generator is operable in conjunction with a secret key which, in a symmetrical encryption technique, is known to the sending station and to an authorized receiving station. The secret key is used at the authorized receiving station to decode the encoded signal received thereat, thereby to recover the informational content of the transmitted signal.
U.S. Pat. No. 4,797,922 discloses a summation generator which generates a pseudo-random sequence. Such pseudo-random sequence is used in the encryption of data. However, the encoded signal is vulnerable to cryptanalysis, at least when driving inputs applied thereto are linear feedback sequences generated by linear feedback shift registers (LFSRs). Output signals generated by the disclosed apparatus exhibit a correlation with a linear combination of input symbols applied by the LFSRs. For example, when four streams of random bits are provided, a correlation coefficient is of the value of 5/24. Because of the correlation, observation of a sufficiently long stream of output symbols can permit the recovery of an otherwise-unknown initial state of the LFSRs. Through such observation, therefore, an unauthorized party might be able successfully to recover the informational content of the transmitted signal. Thereby, the privacy of communications would be compromised.
A manner by which to decrease the correlation exhibited by such conventional apparatus would better assure that an encoded signal could not be decoded by an unauthorized party.
It is in light of this background information related to the generation of encoded signals that the significant improvements of the present invention have evolved.